package com.github.hgkmail.hello.leetcode101.dp.twod;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;

import java.util.ArrayDeque;
import java.util.Queue;

//1 <= m * n <= 10^4
//这种能很快看出选择（choice）的dp题相对好做，这里的choice是上下或者左右，知道[选择]后就容易了，对选择取[max]或[min]
//难点是找出[迭代的方向]：由于有4个取向，需要进行2遍查找，第一次从左上到右下，第二次从右下到左上，相当巧妙！
//从左上到右下: dp[i][j]=min{ dp[i-1][j], dp[i][j-1] }
//从右下到左上: dp[i][j]=min{ dp[i+1][j], dp[i][j+1] }
//最近：近->bfs，最->dp，注意关键词联想。
public class LC542ZeroOneMatrix {

    public int[][] updateMatrix(int[][] mat) {
        //矩阵不一定是正方形，长m和宽n不一定相等
        int m=mat.length;
        if (m<=0) {
            return mat;
        }
        int n=mat[0].length;
        if (n<=0) {
            return mat;
        }
        int[][] dp=new int[m][n];
        //base case
        int max=100000;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j]==0) {
                    dp[i][j]=0;
                } else {
                    dp[i][j]=max;
                }
            }
        }
        //从左上到右下
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j]==0) {
                    continue;
                }
                if (i==0 && j==0) {
                    continue;
                }
                if (i==0) {
                    dp[i][j]=Math.min(dp[i][j], dp[i][j-1]+1);
                    continue;
                }
                if (j==0) {
                    dp[i][j]=Math.min(dp[i][j], dp[i-1][j]+1);
                    continue;
                }
                dp[i][j]=Math.min(dp[i][j], Math.min(dp[i][j-1]+1, dp[i-1][j]+1));
            }
        }
        //从右下到左上
        for (int i = m-1; i >=0; i--) {
            for (int j = n-1; j >=0; j--) {
                if (dp[i][j]==0) {
                    continue;
                }
                if (i==m-1 && j==n-1) {
                    continue;
                }
                if (i==m-1) {
                    dp[i][j]=Math.min(dp[i][j], dp[i][j+1]+1);
                    continue;
                }
                if (j==n-1) {
                    dp[i][j]=Math.min(dp[i][j], dp[i+1][j]+1);
                    continue;
                }
                dp[i][j]=Math.min(dp[i][j], Math.min(dp[i][j+1]+1, dp[i+1][j]+1));
            }
        }

        return dp;
    }

    //找出所有的0，对其进行蔓延（bfs）
    //这里可以看出bfs的[出发点可以不止一个]，这里就有很多出发点，出发点全部都入队。
    public int[][] updateMatrix2(int[][] mat) {
        int m=mat.length;
        if (m<=0) {
            return mat;
        }
        int n=mat[0].length;
        if (n<=0) {
            return mat;
        }
        Queue<int[]> queue=new ArrayDeque<>(m*n);
        int[][] dp=new int[m][n];
        int max=100000;
        int[][] directions={{1,0},{-1,0},{0,1},{0,-1}};
        boolean[][] visited=new boolean[m][n]; //搜索一定要用visited数组，不然会重复搜索，导致stackoverflow。。。
        //把所有的0入队
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j]==0) {
                    dp[i][j]=0;
                    queue.offer(new int[]{i,j});
                } else {
                    dp[i][j]=max;
                }
            }
        }
        int level=-1;
        while (!queue.isEmpty()) {
            int len=queue.size();
            level++;
            while (len>0) {
                int[] ij=queue.poll();
                len--;
                int i=ij[0];
                int j=ij[1];
                dp[i][j]=Math.min(dp[i][j], level);  //level表示层次
                visited[i][j]=true;

                for (int k = 0; k < 4; k++) {
                    int x=i+directions[k][0];
                    int y=j+directions[k][1];
                    if (x>=0 && x<m && y>=0 && y<n && !visited[x][y]) {
                        queue.offer(new int[]{x,y});
                    }
                }
            }
        }

        return dp;
    }

    public static void main(String[] args) {
        int[][] res=new LC542ZeroOneMatrix().updateMatrix2(CommonUtil.parseLc2DArray("[[0,0,0],[0,1,0],[1,1,1]]"));
        CommonUtil.print2DArray(res);
    }
}
